
public class DynamicProgarmming{

	public int findMinCoins(int[] arr, int sum){
		int[] min = new int[sum + 1];
		for(int i = 1; i < min.length; i++){
			min[i] = Integer.MAX_VALUE;
		}
		
		System.out.println("sum: 0" + " is " + min[0]);
		for(int j = 1; j < min.length; j++){
			
			
			for(int k = 0; k < arr.length; k++){
				if(arr[k] <= j && min[j - arr[k]] + 1 < min[j]){
					min[j] = min[j - arr[k]] + 1;
				}
			}
			System.out.println("sum: " + j + " is " + min[j]);
		}
		
		return min[sum];
	}
	
	public String LongestCommonSubstring(String str1, String str2){
		if(str1.length() == 0 || str2.length() == 0){
			return "";
		}
		
		int[][] arr = new int[str1.length()][str2.length()];
		int longestLen = 0;
		int lastSubBegin =0;
		StringBuffer sb = new StringBuffer();
		
		for(int i = 0; i < str1.length(); i++){
			for(int j = 0; j < str2.length(); j++){
				if(str1.charAt(i) == str2.charAt(j)){
				
			/**		
					A B C E A B C D E
				A   1 0 0 0 1 0 0 0 0
				B   0 2 0 0 0 2 0 0 0
				C   0 0 3 0 0 0 3 0 0
				D   0 0 0 0 0 0 0 4 0
				A   1 0 0 0 1 0 0 0 0
				B   0 2 0 0 0 2 0 0 0
				C   0 0 3 0 0 0 3 0 0
				D   0 0 0 0 0 0 0 4 0
				E   0 0 0 0 0 0 0 0 5
			*/
					if(i == 0 || j == 0){
						arr[i][j] = 1;
					}
					else{
						arr[i][j] = arr[i-1][j-1] + 1;
					}
					if(arr[i][j] > longestLen){
						// generate substring from str1 => i
						longestLen = arr[i][j];
						int currentSubBegin = i - arr[i][j] + 1;
						if(lastSubBegin == currentSubBegin){
							sb.append(str1.charAt(i));
						}
						else{
							lastSubBegin = currentSubBegin;
							sb = new StringBuffer();
							sb.append(str1.substring(currentSubBegin, i+1));
						}
					}
					
				}
				
			}
		}
		 return sb.toString();
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {1,3,5};
	    DynamicProgarmming dp = new DynamicProgarmming();
	    System.out.println(dp.findMinCoins(arr, 11));
	    System.out.println(dp.LongestCommonSubstring("ABCDABCDE", "ABCEABCDE"));
	}	

}
